package main.java.com.amanda.suaFa.suafaAll;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Iterator;

/**
 * @author amanda
 * @Description 算法1.3 先进先出队列
 *      这份泛型的Queue实现的基础是链表结构，用于创建任意数据类型的队列，能支持迭代
 */
public class Queue<Item> implements Iterable<Item> {
    private Node first; // 指向最早添加的结点的链接
    private Node last;  // 指向最近添加的结点的链接
    private int N;

    private class Node {
        // 定义了结点的嵌套类
        Item item;
        Node next;
    }
    public boolean isEmpty() {
        return first == null;
    }
    public int size() {
        return N;
    }
    public void enqueue(Item item) {
        // 向队尾添加元素
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty())
            first = last;
        else
            oldLast.next = last;
        N++;
    }
    public Item dequeue() {
        // 从队头删除元素
        Item item = first.item;
        first = first.next;
        if (isEmpty())
            last = null;
        N--;
        return item;
    }

    public static void main(String[] args) {
        // 创建一个队列并操作字符串入列成出列
        Queue<String> q = new Queue<>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (item.equals("-"))
                q.enqueue(item);
            else if (!q.isEmpty())
                StdOut.print(q.dequeue() + " 元素弹出");
        }
        StdOut.println("(" + q.size() + " left on queue)");
    }
    @Override
    public Iterator<Item> iterator() {
        return null;
    }
}
